﻿<HTML>

<HEAD>
  <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8" />  
  <TITLE>Algorithms, Solvers and Configuration Files</TITLE>
  <LINK HREF="doc.css" REL=STYLESHEET>
</HEAD>


<BODY>


<!-- ============================================ -->


  <TABLE CLASS="header">
    <TBODY>
      <TR>
        <TD CLASS="head">Algorithms, Solvers and Configuration Files</TD>
        <TD CLASS="logo" ROWSPAN="2"><IMG CLASS="logosmall" SRC="../images/heo-logo.png"></IMG></TD>
      </TR>
      <TR>
        <TD CLASS="links"><A HREF="heo.html">[Previous]</A><A HREF="projects.html">[Next]</A><A HREF="../index.html">[Home]</A></TD>
      </TR>
    </TBODY>
  </TABLE>


  <H2>Contents</H2>

  <UL>
    <LI><A HREF="#solvers">Solvers</A></LI>
    <LI><A HREF="#config">Configuration Files</A></LI>
    <LI><A HREF="#ga">GA (Genetic Algorithm)</A></LI> 
    <LI><A HREF="#sa">SA (Simulated Annealing)</A></LI> 
    <LI><A HREF="#hybrids">Hybrid Algorithms</A></LI> 
  </UL>


<!-- ============================================ -->


  <A NAME="solvers"></A>
  <H3>Solvers</H3>

  <P>
    As it was mentioned in the previous section, two optimization methods are provided in the library: GA and SA.
    Solvers implement these methods using different parallel programming techniques: MPI or OpenMP.
    At present, there are four solvers in the library: <TT>GA_MPI</TT>, <TT>GA_OMP</TT>, <TT>SA_MPI</TT>, <TT>SA_OMP</TT>.
    All these solvers use the so-called <B>multistart model</B> for parallel computations which consists in running several cooperative threads that exchange information during execution.
  </P>

  <P>
    The cooperation of the threads may be asynchronous or synchronous.
    The synchronous cooperation is performed with the fixed rate and temporal threads blocking.
    The asynchronous cooperation is originated with the fixed rate by the first thread and is performed without threads blocking.
    Both cooperation modes are presented on the figure below (asynchronous mode is on the left).
  </P>

  <IMG SRC="../images/cooperation.png" WIDTH="800px"></IMG>

   <P>
  </P>

<!-- ============================================ -->

  <A NAME="config"></A>
  <H3>Configuration Files</H3>

  <P>
    The behavior of the solvers is controlled by the the user with the help of the <TT>*.xml</TT> configuration files which store all parameters as attributes of different <B>nodes</B> in a tree-like structure.
    Some of these parameters are algorithm-specific, some are problem-specific, and the others are common to all optimization methods and solvers.
    Below is a brief description of the nodes and their attributes that contain parameters common to all solvers and projects.
  </P>

  <P>
    <TT><B>&lt;run.../&gt;<B></TT>
  </P>

  <TABLE>
    <TBODY>
      <TR>
        <TH>Attribute</TH>
        <TH>Type</TH>
        <TH>Description</TH>
        <TH>Default Value</TH>
      </TR>

      <TR>
        <TD><TT>initial_solution</TT></TD>
        <TD ALIGN="center">string</TD>
        <TD>Name of the file containing initial solution(s). Empty name means that initial solution(s) should be generated automatically.</TD>
        <TD ALIGN="center">""</TD>
      </TR>

      <TR>
        <TD><TT>run_count</TT></TD>
        <TD ALIGN="center">int</TD>
        <TD>Number of the solver runs.</TD>
        <TD ALIGN="center">1</TD>
      </TR>

      <TR>
        <TD><TT>debug_level</TT></TD>
        <TD ALIGN="center">int</TD>
        <TD>Debug level: 0 &mdash; low verbosity; 1 &mdash; high verbosity.</TD>
        <TD ALIGN="center">0</TD>
      </TR>
    </TBODY>
  </TABLE>

  <P>
    The other two attributes of this node are: <TT>input_file</TT> and <TT>output_dir</TT>.
    The first one is used to define the name of the problem instance file (e.g., <TT>input_file="../../../problems/maxsat/sample.cnf"</TT> or <TT>input_file=""</TT> if the problem does not need such file).
    The second one is used to define the output folder for the project.
    By default, it is <TT>"../res/"</TT> for problems that do not need an input file, otherwise it is <TT>"../res/file_name"</TT> where <TT>file_name</TT> is the name of the problem instance file without extension (e.g., <TT>output_dir="../res/sample"</TT>).
  </P>


  <P>
    <TT><B>&lt;coop.../&gt;</B></TT>
  </P>


  <TABLE>
    <TBODY>
      <TR>
        <TH>Attribute</TH>
        <TH>Type</TH>
        <TH>Description</TH>
        <TH>Default Value</TH>
      </TR>

      <TR>
        <TD><TT>async_mode</TT></TD>
        <TD ALIGN="center">bool</TD>
        <TD>Turn ON/OFF asynchronous mode: false &mdash; synchronous mode; true &mdash; asynchronous mode.</TD>
        <TD ALIGN="center">false</TD>
      </TR>

      <TR>
        <TD><TT>cooperation_rate</TT></TD>
        <TD ALIGN="center">int</TD>
        <TD>Threads cooperation rate.</TD>
        <TD ALIGN="center">25</TD>
      </TR>
    </TBODY>
  </TABLE>


  <P>
    <TT><B>&lt;stop_condition&gt;...&lt;/stop_condition&gt;</B></TT>
  </P>

  <P>
    The aim of this node is to provide the solver with the stop conditions.
    These conditions may be of different nature.
    At present two types of stop conditions are implemented: the maximum number of steps made by the solver and the cost limit.
    Their parameters are stored as attributes of the sub-nodes <TT>&lt;max_step.../&gt;</TT> and <TT>&lt;cost_limit.../&gt;</TT> respectively.
    The default value for the first one is of int type and equals to 100.
    The default value for the second equals to zero (it has the TCostType).
  </P>

<!-- ============================================ -->


  <A NAME="ga"></A>
  <H3>GA (Genetic Algorithm)</H3>

  <P>
    The genetic algorithm (GA) is a well-known optimization technique that describes the optimization process in terms of the evolving population of chromosomes.
    The sequential version of this algorithm is shown below:
  </P>

  <DIV CLASS="code">
    &nbsp;1: <I>Population</I> := InitialPopulation()<BR>
    &nbsp;2: <B>for all</B> &alpha;<SUB>i</SUB>&isin;<I>Population</I> <B>do</B><BR>
    &nbsp;3: &nbsp;&nbsp;EvaluateFitness(&alpha;<SUB>i</SUB>)<BR>
    &nbsp;4: <B>end for</B><BR>
    &nbsp;5: <B>while not</B> StopCondition() <B>do</B><BR>
    &nbsp;6: &nbsp;&nbsp;<I>Parents</I> := SelectParents(<I>Population</I>)<BR>
    &nbsp;7: &nbsp;&nbsp;<I>Offspring</I> := Crossover(<I>Parents</I>)<BR>
    &nbsp;8: &nbsp;&nbsp;<I>Offspring</I> := Mutation(<I>Offspring</I>)<BR>
    &nbsp;9: &nbsp;&nbsp;<B>for all</B> &beta;<SUB>i</SUB>&isin;<I>Offspring</I> <B>do</B><BR>
         10: &nbsp;&nbsp;&nbsp;&nbsp;EvaluateFitness(&beta;<SUB>i</SUB>)<BR>
         11: &nbsp;&nbsp;<B>end for</B><BR>
         12: &nbsp;&nbsp;<I>Population</I> := UpdatePopulation(<I>Parents</I>&cup;<I>Offspring</I>)<BR>
         13: <B>end while</B><BR>
         14: <I>Solution</I> := ChooseBestOf(<I>Population</I>)<BR>
    <B>Ensure:</B> <I>Solution</I>
  </DIV>


  <P>
    The multistart model for the genetic algorithm is similar to the so-called island model.
    In this model separate populations (islands) of the same size are evolved by concurrently running threads that periodically cooperate with each other.
  </P> 

  <P>
    The following table lists the GA parameters that are stored as attributes of the <TT>&lt;ga...&gt;...&lt;/ga&gt;</TT> node of the configuration file. 
  </P>


  <TABLE>
    <TBODY>
      <TR>
        <TH>Attribute</TH>
        <TH>Type</TH>
        <TH>Description</TH>
        <TH>Default Value</TH>
      </TR>

      <TR>
        <TD><TT>population_size</TT></TD>
        <TD ALIGN="center">int</TD>
        <TD>Population size. In the island model this parameter indicates the population size for each island.</TD>
        <TD ALIGN="center">30</TD>
      </TR>

      <TR>
        <TD><TT>offspring_size</TT></TD>
        <TD ALIGN="center">int</TD>
        <TD>Offspring size. In the island model this parameter indicates the offspring size for each island.</TD>
        <TD ALIGN="center">50</TD>
      </TR>

      <TR>
        <TD><TT>only_offspring</TT></TD>
        <TD ALIGN="center">bool</TD>
        <TD>Select only offspring into the next population.</TD>
        <TD ALIGN="center">false</TD>
      </TR>
 
      <TR>
        <TD><TT>migration_size</TT></TD>
        <TD ALIGN="center">int</TD>
        <TD>Number of migrants for the island model.</TD>
        <TD ALIGN="center">3</TD>
      </TR>

      <TR>
        <TD><TT>output_size</TT></TD>
        <TD ALIGN="center">int</TD>
        <TD>Number of solutions to be written into the solution pool after execution.</TD>
        <TD ALIGN="center">1</TD>
      </TR>
   </TBODY>
  </TABLE>


  <P>
    The <TT>&lt;ga...&gt;...&lt;/ga&gt;</TT> node has several sub-nodes. 
    The brief description of these sub-nodes is given in the table below.
  </P>


  <TABLE>
    <TBODY>
      <TR>
        <TH>Node name</TH>
        <TH>Description</TH>
      </TR>

      <TR>
        <TD><TT>parent_selection</TT></TD>
        <TD>Parents selection method and its parameters.</TD>
      </TR>

      <TR>
        <TD><TT>offspring_selection</TT></TD>
        <TD>Survivals selection method and its parameters.</TD>
      </TR>

      <TR>
        <TD><TT>emigrate_selection</TT></TD>
        <TD>Migrants selection method and its parameters.</TD>
      </TR>
 
      <TR>
        <TD><TT>immigrate_selection</TT></TD>
        <TD>Method of selecting chromosomes for replacement by migrants and its parameters.</TD>
      </TR>

      <TR>
        <TD><TT>operator</TT></TD>
        <TD>The list of genetic operators and their parameters (contains crossover and mutation operators by default).</TD>
      </TR>

      <TR>
        <TD><TT>stop_condition</TT></TD>
        <TD>Stop conditions (see <A HREF="#config">Configuration files</A> above).</TD>
      </TR>

      <TR>
        <TD><TT>coop</TT></TD>
        <TD>Cooperation mode (see <A HREF="#config">Configuration files</A> above).</TD>
      </TR>
   </TBODY>
  </TABLE>

  <P>
    At present three types of selection methods are available: random, tournament and roulette wheel (see the <TT>*.xml</TT> files of the sample projects for examples). 
    The list of genetic operators can include in any order: crossover, mutation, SA or user-defined operators.
  </P>

<!-- ============================================ -->


  <A NAME="sa"></A>
  <H3>SA (Simulated Annealing)</H3>

 
  <P>
     The simulated annealing (SA) exploits an analogy between two processes: the process of obtaining low-energy states of a solid and the search for a minimum in a discrete system.
    It may be sketched in pseudocode as follows:
  </P> 

  <DIV CLASS="code">
    &nbsp;1: <I>Solution</I> := InitialSolution()<BR>
    &nbsp;2: <I>BestSolution</I> := <I>Solution</I><BR>
    &nbsp;3: <I>BestCost</I> := Cost(<I>Solution</I>)<BR>
    &nbsp;4: <I>T</I> := InitialTemperature()<BR>
    &nbsp;5: <I>k</I> := 0<BR>
    &nbsp;6: <B>while not</B> StopCondition() <B>do</B><BR>
    &nbsp;7: &nbsp;&nbsp;<I>NewSolution</I> := ChooseRandomOf(Neighborhood(<I>Solution</I>))<BR>
    &nbsp;8: &nbsp;&nbsp;<I>NewSolution</I> := Cost(<I>Solution</I>)<BR>
    &nbsp;9: &nbsp;&nbsp;<B>if</B> <I>NewCost</I> < <I>BestCost</I> <B>then</B><BR>
         10: &nbsp;&nbsp;&nbsp;&nbsp;<I>BestSolution</I> := <I>NewSolution</I><BR>
         11: &nbsp;&nbsp;&nbsp;&nbsp;<I>BestCost</I> := <I>NewCost</I><BR>
         12: &nbsp;&nbsp;<B>end if</B><BR>
         13: &nbsp;&nbsp;<I>Solution</I> := AcceptWithProbability(<I>Solution</I>, <I>NewSolution</I>, <I>T</I>)<BR>
         14: &nbsp;&nbsp;<I>k</I> := <I>k</I> + 1<BR>
         15: &nbsp;&nbsp;<I>T</I> := UpdateTemperature(<I>T</I>, <I>k</I>)<BR>
         16: <B>end while</B><BR>
    <B>Ensure:</B> <I>BestSolution</I>
  </DIV>


  <P>
    The multistart model for the SA consists in running several cooperative SA that exchange information on their steps during execution.
  </P> 

  <P>
    The SA parameters are stored as attributes of the <TT>&lt;sa...&gt;...&lt;/sa&gt;</TT> node. 
  </P>


  <TABLE>
    <TBODY>
      <TR>
        <TH>Attribute</TH>
        <TH>Type</TH>
        <TH>Description</TH>
        <TH>Default Value</TH>
      </TR>

      <TR>
        <TD><TT>move_probability</TT></TD>
        <TD ALIGN="center">double</TD>
        <TD>Move probability.</TD>
        <TD ALIGN="center">0.02</TD>
      </TR>

      <TR>
        <TD><TT>initial_temperature<TT></TD>
        <TD ALIGN="center">double</TD>
        <TD>Initial temperature.</TD>
        <TD ALIGN="center">1.0</TD>
      </TR>

      <TR>
        <TD><TT>cooling_rate<TT></TD>
        <TD ALIGN="center">double</TD>
        <TD>Cooling rate.</TD>
        <TD ALIGN="center">0.994</TD>
      </TR>

      <TR>
        <TD><TT>heating_rate<TT></TD>
        <TD ALIGN="center">double</TD>
        <TD>Heating rate.</TD>
        <TD ALIGN="center">1.5</TD>
      </TR>

      <TR>
        <TD><TT>isotherm_moves<TT></TD>
        <TD ALIGN="center">int</TD>
        <TD>Number of moves for each isotherm.</TD>
        <TD ALIGN="center">20</TD>
      </TR>
 
      <TR>
        <TD><TT>update_policy<TT></TD>
        <TD ALIGN="center">int</TD>
        <TD>Solution updating policy: 0 &mdash; keep best solution; 1 &mdash; do not keep best solution (classic SA).</TD>
        <TD ALIGN="center">0</TD>
      </TR>
    </TBODY>
  </TABLE>

  <P>
    The <TT>&lt;sa...&gt;...&lt;/sa&gt;</TT> node also includes <TT>&lt;coop.../&gt;</TT> and <TT>&lt;stop_condition&gt;...&lt;/stop_condition&gt;</TT> sub-nodes (see <A HREF="#config">Configuration files</A> above).
  </P>


<!-- ============================================ -->


  <A NAME="hybrids"></A>
  <H3>Hybrid algorithms</H3>

 
  <P>
    All HeO solvers a hybridization-ready.
    This means that they may be combined with each other to obtain new hybrid algorithms.
    There are two types of hybridization in the library: <B>weak</B> and <B>strong</B>.
  </P> 

  <P>
    Weak hybridization means that the output of one solver serves as the input of the other solver.
    This is achived by the means of the solution pool.
    The size of the produced pool is controlled by the <TT>output_size</TT> parameter of the solvers.
  </P> 

  <P>
    Strong hybridization means that some solvers can include other solvers as their parts.
    Such included solvers are called <B>operators</B>.
    At present only the GA solvers allow to construct such hybrids (see sample projects for examples).
  </P> 


<!-- ============================================ -->


<H2>&nbsp;</H2>

<A HREF="heo.html">[Previous]</A><A HREF="projects.html">[Next]</A><A HREF="../index.html">[Home]</A>


<!-- ============================================ -->


</BODY>

</HTML>


